/**
 * 29.两数相除
 * 
 * 给定两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 * 返回被除数dividend除以除数divisor得到的商。
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 * 
 * 示例1:
 * 输入: dividend = 10, divisor = 3
 * 输出: 3
 * 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
 * 
 * 示例2:
 * 输入: dividend = 7, divisor = -3
 * 输出: -2
 * 解释: 7/-3 = truncate(-2.33333..) = -2
 * 
 * 提示：
 * 被除数和除数均为 32 位有符号整数。
 * 除数不为0。
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31− 1]。本题中，如果除法结果溢出，则返回2^31− 1。
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/divide-two-integers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
package zw;

class T29 {
    public static int divide(int dividend, int divisor) {  // 超时
        int result = 0;
        int tempDividend;
        int tempDivisor;
        tempDividend = dividend < 0 ? -dividend : dividend;
        tempDivisor = divisor < 0 ? -divisor : divisor;
        while((tempDividend - tempDivisor) >= 0) {
            tempDividend -= tempDivisor;
            result++;
        }
        if((dividend ^ divisor) < 0) {
            return -result;
        } else if(result < 0){  // result<0说明正数溢出
            return 2147483647;
        } else {
            return result;
        }
    }

    public static int divide1(int dividend, int divisor) {
        if(dividend == -2147483648 && divisor == 1) {
            return -2147483648;
        } else if(dividend == -2147483648 && divisor == -1) {
            return 2147483647;
        } else if(dividend == -2147483648 && divisor == -2147483648) {
            return 1;
        } else if(divisor == -2147483648) {
            return 0;
        }
        int fix = 0;
        if(dividend == -2147483648) {
            if(divisor > 0) {
                dividend += divisor;
            } else {
                dividend -= divisor;
            }
            fix++;
        }
        int tempDividend;
        int tempDivisor;
        int result;
        tempDividend = dividend < 0 ? -dividend : dividend;
        tempDivisor = divisor < 0 ? -divisor : divisor;
        result = posDivide1(tempDividend, tempDivisor);
        if((dividend ^ divisor) < 0) {
            return -(result + fix);
        } else {
            return result + fix;
        }
    }

    private static int posDivide1(int dividend, int divisor) {
        int tempDivisor = divisor;
        int result = 1;
        if (dividend == divisor) {
            return 1;
        } else if (dividend < divisor) {
            return 0;
        }
        while (dividend >= (tempDivisor << 1) && (tempDivisor << 1) > 0) {
            result <<= 1;
            tempDivisor <<= 1;
        }
        return result + posDivide1(dividend - tempDivisor, divisor);
    }
}
